n,l,k=map(int,input().split())
a=list(map(int,input().split()))+[l]
b=list(map(int,input().split()))+[0]
dp={}
def dfs(i,k,p):
if (i,k,p) in dp:
return dp[(i,k,p)]
if i==n:
return 0
res=float("inf")
if k>0 and b[i]>p:
res=min(res,p*(a[i+1]-a[i])+dfs(i+1,k-1,p))
res=min(res,b[i]*(a[i+1]-a[i])+dfs(i+1,k,b[i]))
dp[(i,k,p)]=res
return res
print(a[1]*b[0]+dfs(1,k,b[0]))
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define int long long
#define all(x) x.begin(), x.end()
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 5e2 + 5, mod = 1e9 + 7;
int tc, n, m, k, ans, a[N], dp[N][N], d[N], l;
string s, t;
bool flag, vis[N], pr[N];
int32_t main(){
FASTER;
// freopen("", "r", stdin);
tc=1;
// cin>>tc;
while(tc--){
cin>>n>>l>>k;
d[n+1] = l;
for(int i=1; i<=n; i++)cin>>d[i];
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=0; i<=n+1; i++)
for(int j=0; j<=k; j++)
dp[i][j] = 1e10;
dp[1][0] = a[1] * d[2];
for(int i=2; i<=n+1; i++){
for(int j=0; j<=min(i-2, k); j++){
for(int lst=i-j-1; lst<i; lst++)
dp[i][j] = min(dp[i][j], dp[lst][j-i+lst+1] + (d[i] - d[lst+1]) * a[lst] + (d[i+1] - d[i]) * a[i]);
}
}
ans = 1e10;
for(int i=0; i<=k; i++)ans = min(ans, dp[n+1][i]);
cout<<ans<<endl;
}
return 0;
}
822B - Crossword solving | 1623A - Robot Cleaner |
884B - Japanese Crosswords Strike Back | 862B - Mahmoud and Ehab and the bipartiteness |
429A - Xor-tree | 1675C - Detective Task |
950A - Left-handers Right-handers and Ambidexters | 672B - Different is Good |
1C - Ancient Berland Circus | 721A - One-dimensional Japanese Crossword |
1715B - Beautiful Array | 60B - Serial Time |
453A - Little Pony and Expected Maximum | 1715A - Crossmarket |
1715C - Monoblock | 1512C - A-B Palindrome |
1679B - Stone Age Problem | 402A - Nuts |
792A - New Bus Route | 221A - Little Elephant and Function |
492C - Vanya and Exams | 1369B - AccurateLee |
892B - Wrath | 999A - Mishka and Contest |
727C - Guess the Array | 1625C - Road Optimization |
1715D - 2+ doors | 267A - Subtractions |
1582A - Luntik and Concerts | 560A - Currency System in Geraldion |